/*
题目: 获取所有钥匙的最短路径
给定一个二维网格 grid ，其中：

    '.' 代表一个空房间
    '#' 代表一堵
    '@' 是起点
    小写字母代表钥匙
    大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
https://leetcode.cn/problems/shortest-path-to-get-all-keys/description/
 */
public class ShortestPathAllKeys {
    private static int[] dir = new int[] {0, -1, 0, 1, 0}; // 方向数组
    // 将钥匙 映射 为一个下标
    private Map<Character, Integer> keyIdx = new HashMap<> ();

    public int shortestPathAllKeys(String[] grid) {
        int row = grid.length, col = grid[0].length();

        // 预处理钥匙的序号 和 起点位置
        int sx = 0, sy = 0;
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; j ++) {
                char c = grid[i].charAt(j);
                if (c == '@') {
                    sx = i;
                    sy = j;
                } else if (Character.isLowerCase(c)) {
                    keyIdx.put(c, keyIdx.size());
                }
            }
        }

        // 表示到达 grid[i][j], 并且 钥匙情况为 mark 的时候, 的步数
        int[][][] dist = new int[row][col][1 << keyIdx.size()];
        for (int i = 0; i < row; i ++)
            for (int j = 0; j < col; j ++)
                Arrays.fill(dist[i][j], -1); // 刚开始哪里都到不了

        dist[sx][sy][0] = 0; // 出发
        Queue<int[]> queue = new LinkedList<> ();
        queue.offer(new int[] {sx, sy, 0});

        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            int x = p[0], y = p[1], mark = p[2];
            for (int i = 0; i < 4; i ++) {
                int nx = x + dir[i], ny = y + dir[i + 1];
                // 越界 或者 是墙
                if (nx < 0 || nx >= row || ny < 0 || ny >= col || grid[nx].charAt(ny) == '#')
                    continue ;

                // 至此, 下一步要开始分情况讨论
                char nextCh = grid[nx].charAt(ny);
                if (nextCh == '.' || nextCh == '@') { // 如果啥都不是
                    if (dist[nx][ny][mark] == -1) { // 如果没有到达过这里
                        dist[nx][ny][mark] = dist[x][y][mark] + 1;
                        queue.offer(new int[] {nx, ny, mark});
                    }
                } else if (Character.isLowerCase(nextCh)) { // 如果是钥匙
                    // 拿到钥匙后的 状态
                    int nextMark = mark | (1 << keyIdx.get(nextCh));
                    if (dist[nx][ny][nextMark] == -1) { // 如果没有到达过
                        dist[nx][ny][nextMark] = dist[x][y][mark] + 1;
                        if (nextMark == (1 << keyIdx.size()) - 1) { // 如果下一个状态就是拿到所有钥匙了, 返回即可
                            return dist[nx][ny][nextMark];
                        }
                        queue.offer(new int[] {nx, ny, nextMark});
                    }
                } else { // 如果是锁
                    if ((mark >> keyIdx.get(Character.toLowerCase(nextCh)) & 1) == 1) { // 如果有这个钥匙才继续往前走
                        if (dist[nx][ny][mark] == -1) {  //如果没有走过, 才继续往前走
                            dist[nx][ny][mark] = dist[x][y][mark] + 1;
                            queue.offer(new int[] {nx, ny, mark});
                        }
                    }
                }
            }
        }
        return -1;
    }
}
